Giả sử G = ( ( V , E ) , c , s , t ) {\displaystyle G=((V,E),c,s,t)} là một mạng lưới với khả năng thông qua c ( u , v ) {\displaystyle c(u,v)} và luồng f ( u , v ) {\displaystyle f(u,v)} trên cung ( u , v ) {\displaystyle (u,v)} .
Khả năng thông qua còn dư là một ánh xạ c f : V × V → R + {\displaystyle c_{f}:V\times V\to R^{+}} định nghĩa như sau,
- nếu ( u , v ) ∈ E {\displaystyle (u,v)\in E} , thì c f ( u , v ) = c ( u , v ) − f ( u , v ) {\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)} c f ( v , u ) = f ( u , v ) {\displaystyle c_{f}(v,u)=f(u,v)}
- c f ( u , v ) = 0 {\displaystyle c_{f}(u,v)=0} nếu không phải.
Đồ thị còn dư là đồ thị G f = ( ( V , E f ) , c f | E f , s , t ) {\displaystyle G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)} , trong đó E f = { ( u , v ) ∈ V × V : c f ( u , v ) > 0 } {\displaystyle E_{f}=\{(u,v)\in V\times V:c_{f}(u,v)>0\}} .Một
đường tăng luồng là một đường s − t {\displaystyle s-t} trên đồ thị còn dư G f {\displaystyle G_{f}} .Định nghĩa dist ( v ) {\displaystyle \operatorname {dist} (v)} là độ dài đường đi ngắn nhất (tính theo số cung) từ s {\displaystyle s} đến v {\displaystyle v} trên G f {\displaystyle G_{f}} .
Đồ thị tầng của G f {\displaystyle G_{f}} là đồ thị G L = ( V , E L , c f | E L , s , t ) {\displaystyle G_{L}=(V,E_{L},c_{f}|_{E_{L}},s,t)} , trong đó E L = { ( u , v ) ∈ E f : dist ( v ) = dist ( u ) + 1 } {\displaystyle E_{L}=\{(u,v)\in E_{f}:\operatorname {dist} (v)=\operatorname {dist} (u)+1\}} .Một
luồng ngăn chặn là một luồng f ′ {\displaystyle f'} từ s {\displaystyle s} đến t {\displaystyle t} trên đồ thị G L {\displaystyle G_{L}} sao cho đồ thị G ′ = ( V , E L ′ , s , t ) {\displaystyle G'=(V,E_{L}',s,t)} với E L ′ = { ( u , v ) : f ′ ( u , v ) < c f | E L ( u , v ) } {\displaystyle E_{L}'=\{(u,v):f'(u,v)<c_{f}|_{E_{L}}(u,v)\}} không có đường s − t {\displaystyle s-t} nào.
